package 题目集.滑动窗口;

import org.junit.Test;
import 题目集.位运算.集合论.demo01_找到按位或最接近K的子数组;

/**
 * https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/description/?envType=daily-question&envId=2024-10-09
 * 给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，
 * 满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。
 * 请你返回 最小 的绝对差值。
 * 子数组 是数组中连续的 非空 元素序列。
 */
public class demo02_找到按位或最接近K的子数组 {
    @Test
    public void t1() {
        int[] nums = {3, 3, 8};
        System.out.println(minimumDifference(nums, 8) == 0);
    }

    @Test
    public void t2() {
        int[] nums = {42, 70, 64, 40, 36};
        System.out.println(minimumDifference(nums, 88) == 16);
    }

    @Test
    public void t3() {
        int[] nums = {6};
        System.out.println(minimumDifference(nums, 2));
    }

    int[] arr = new int[31];

    int val = 0;

    /**
     * 第一思路：枚举所有区间，时间复杂度n^2
     * 优解：滑动窗口
     * 如果串口右扩，则or操作的结果越大，左缩则越小。可以通过这种方式来找到最接近K的区间。
     * 但此题有个难点，就是串口左缩时，无法做逆运算。
     * 所以可以用之前的计数方式，记录每个二进制位有多少个1，左缩的时候把这些1给去掉，再求一次二进制的值即可
     *
     * 这题还有集合论的解法{@link demo01_找到按位或最接近K的子数组#minimumDifference(int[], int)}
     * @param nums
     * @param k
     * @return
     */
    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int l = 0, r = 0; r < nums.length; r++) {
            or(nums[r]);
            while (val >= k && l <= r) {
                res = Math.min(res, val - k);
                unOr(nums[l++]);
            }
            /*如果区间内的元素>=1个*/
            if (l <= r) {
                res = Math.min(res, k - val);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     * 或运算
     *
     * @param v
     * @return
     */
    public void or(int v) {
        val |= v;
        for (int i = 0; v > 0; i++, v = v >> 1) {
            arr[i] += v & 1;
        }
    }

    /**
     * 或运算求逆
     *
     * @param v
     * @return
     */
    public void unOr(int v) {
        for (int i = 0, x = 1; v > 0; i++, x = x << 1, v = v >> 1) {
            arr[i] -= v & 1;
            if (arr[i] == 0) {
                val &= ~x;
            }
        }
    }

}
